Search for: All records

Abstract Counting independent sets in graphs and hypergraphs under a variety of restrictions is a classical question with a long history. It is the subject of the celebrated container method which found numerous spectacular applications over the years. We consider the question of how many independent sets we can have in a graph under structural restrictions. We show that any$$n$$-vertex graph with independence number$$\alpha$$without$$bK_a$$as an induced subgraph has at most$$n^{O(1)} \cdot \alpha ^{O(\alpha )}$$independent sets. This substantially improves the trivial upper bound of$$n^{\alpha },$$whenever$$\alpha \le n^{o(1)}$$and gives a characterisation of graphs forbidding which allows for such an improvement. It is also in general tight up to a constant in the exponent since there exist triangle-free graphs with$$\alpha ^{\Omega (\alpha )}$$independent sets. We also prove that if one in addition assumes the ground graph is chi-bounded one can improve the bound to$$n^{O(1)} \cdot 2^{O(\alpha )}$$which is tight up to a constant factor in the exponent. 

Let G be a Berge graph that has no odd prism and no antihole of length at least six as an induced subgraph. We show that every such graph G with no balanced skew-partition is either complete or has an even pair. 

The celebrated Erdős-Pósa Theorem, in one formulation, asserts that for every c ∈ N, graphs with no subgraph (or equivalently, minor) isomorphic to the disjoint union of c cycles have bounded treewidth. What can we say about the treewidth of graphs containing no induced subgraph isomorphic to the disjoint union of c cycles? Let us call these graphs c-perforated. While 1-perforated graphs have treewidth one, complete graphs and complete bipartite graphs are examples of 2-perforated graphs with arbitrarily large treewidth. But there are sparse examples, too: Bonamy, Bonnet, Déprés, Esperet, Geniet, Hilaire, Thomassé and Wesolek constructed 2-perforated graphs with arbitrarily large treewidth and no induced subgraph isomorphic to K3 or K3,3; we call these graphs occultations. Indeed, it turns out that a mild (and inevitable) adjustment of occultations provides examples of 2-perforated graphs with arbitrarily large treewidth and arbitrarily large girth, which we refer to as full occultations. Our main result shows that the converse also holds: for every c ∈ N, a c-perforated graph has large treewidth if and only if it contains, as an induced subgraph, either a large complete graph, or a large complete bipartite graph, or a large full occultation. This distinguishes c-perforated graphs, among graph classes purely defined by forbidden induced subgraphs, as the first to admit a grid-type theorem incorporating obstructions other than subdivided walls and their line graphs. More generally, for all c, o ∈ N, we establish a full characterization of induced subgraph obstructions to bounded treewidth in graphs containing no induced subgraph isomorphic to the disjoint union of c cycles, each of length at least o + 2. 

A clock is a graph consisting of an induced cycle and a vertex not in with at least two non-adjacent neighbours in . We show that every clock-free graph of large treewidth contains a “basic obstruction” of large treewidth as an induced subgraph: a complete graph, a subdivision of a wall, or the line graph of a subdivision of a wall. 

We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An even pair in a graph is a pair of vertices all induced paths between which are even. An even set is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator which is the union of a bounded number of even sets, where the bound depends only on the maximum degree of the graph. This allows us to solve the maximum weight independent set problem using the well-known submodular function minimization algorithm. Funding: This work was supported by the Engineering and Physical Sciences Research Council [Grant EP/V002813/1]; the National Science Foundation [Grants DMS-1763817, DMS-2120644, and DMS-2303251]; and Alexander von Humboldt-Stiftung. 

Given c ∈ N, we say a graph G is c-pinched if G does not contain an induced subgraph consisting of c cycles, all going through a single common vertex and otherwise pairwise disjoint and with no edges between them. What can be said about the structure of c-pinched graphs? For instance, 1-pinched graphs are exactly graphs of treewidth 1. However, bounded treewidth for c > 1 is immediately seen to be a false hope because complete graphs, complete bipartite graphs, subdivided walls and line graphs of subdivided walls are all examples of 2-pinched graphs with arbitrarily large treewidth. There is even a fifth obstruction for larger values of c, discovered by Pohoata and later independently by Davies, consisting of 3-pinched graphs with unbounded treewidth and no large induced subgraph isomorphic to any of the first four obstructions. We fuse the above five examples into a grid-type theorem fully describing the unavoidable induced subgraphs of pinched graphs with large treewidth. More precisely, we prove that for every c ∈ N, a c-pinched graph G has large treewidth if and only if G contains one of the following as an induced subgraph: a large complete graph, a large complete bipartite graph, a subdivision of a large wall, the line graph of a subdivision of a large wall, or a large graph from the Pohoata-Davies construction. Our main result also generalizes to an extension of pinched graphs where the lengths of excluded cycles are lower-bounded. 

We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constant c > 0 such that for every integer n > 1 every n-vertex even-hole-free graph has a tree decomposition where each bag has stability (independence) number at most clog10 n. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems that are known to be NP-hard in general, can be solved in quasipolynomial time if the input graph is even-hole-free. The quasi-polynomial complexity will remain the same even if the exponent of the logarithm is reduced to 1 (which would be asymptotically best possible). 

Sivaraman (2020) conjectured that if G is a graph with no induced even cycle then there exist sets X1,X2⊆V(G) satisfying V(G)=X1∪X2 such that the induced graphs G[X1] and G[X2] are both chordal. We prove this conjecture in the special case where G contains no sector wheel, namely, a pair (H,w) where H is an induced cycle of G and w is a vertex in V(G)∖V(H) such that N(w)∩H is either V(H) or a path with at least three vertices. 

Unlike minors, the induced subgraph obstructions to bounded treewidth come in a large variety, including, for every t ∈ N, the t-basic obstructions: the graphs Kt+1 and Kt,t, along with the subdivisions of the t-by-t wall and their line graphs. But this list is far from complete. The simplest example of a “non-basic” obstruction is due to Pohoata and Davies (independently). For every n ∈ N, they construct certain graphs of treewidth n and with no 3-basic obstruction as an induced subgraph, which we call n-arrays. Let us say a graph class G is clean if the only obstructions to bounded treewidth in G are in fact the basic ones. It follows that a full description of the induced subgraph obstructions to bounded treewidth is equivalent to a characterization of all families H of graphs for which the class of all H-free graphs is clean (a graph G is H-free if no induced subgraph of G is isomorphic to any graph in H). This remains elusive, but there is an immediate necessary condition: if H-free graphs are clean, then there are only finitely many n ∈ N such that there is an n-array which is H-free. The above necessary condition is not sufficient in general. However, the situation turns out to be different if H is finite: we prove that for every finite set H of graphs, the class of all H-free graphs is clean if and only if there is no H-free n-array except possibly for finitely many values of n. 

Given a graph H, we prove that every (theta, prism)-free graph of sufficiently large treewidth contains either a large clique or an induced subgraph isomorphic to H, if and only if H is a forest.